import java.util.Comparator;

public class HeapSort<T> {
    private Comparator<T> comparator;

    public HeapSort(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    public void imp(T[] array) {
        heapify(array);
        for (int i = 0; i < array.length; i++) {
            swap(array, array.length - i - 1, 0);

            siftDown(array, array.length - i - 1, 0);
        }
    }

    private void heapify(T[] array) {
        for (int i = (array.length >> 1); i >= 0; i--) {
            siftDown(array, array.length, i);
        }
    }

    private void siftDown(T[] array, int size, int index) {
        for (int i = index; i <= (size >> 1) - 1; ) {
            int childIndex = (i << 1) + 1;
            T childElement = array[childIndex];
            int rightChildIndex = childIndex + 1;
            if (rightChildIndex <= size - 1 && comparator.compare(array[rightChildIndex], childElement) > 0) {
                childIndex = rightChildIndex;
            }

            if (comparator.compare(array[childIndex], array[i]) < 0) {
                break;
            } else {
                swap(array, i, childIndex);
            }
            i = childIndex;
        }
    }

    private static <T> void swap(T[] array, int i, int j) {
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
